class Solution {
    public int mySqrt(int x) {
        long left=0,right=x,mid;
        while(left<right){
            mid=(right-left)/2+left;
            if(mid*mid<x) left=mid+1;
            else right=mid;
        }

        if(left*left==x) return (int)left;
        return (int)left-1;
    }
}


class Solution1 {
    public int searchInsert(int[] nums, int target) {

        if(nums[nums.length-1]<target) return nums.length;


        int left=0,right=nums.length-1,mid;
        while(left<right){
            mid=(right-left)/2+left;
            if(nums[mid]<target) left=mid+1;
            else right=mid;
        }


        return right;
    }
}